package com.leetcode.partition3;

import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/7/31 8:44
 */
public class LC287寻找重复数 {

    public static int findDuplicate(int[] nums) {
        return method2(nums);
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 2, 2 };
        System.out.println(findDuplicate(nums));
    }

    //快慢指针法
    private static int method2(int[] nums) {
        if (nums.length == 0) return 0;
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    //哈希表法
    private static int hashtableMethod(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        for (int num : nums) {
            if (map.containsKey(num)) return num;
            map.put(num, 0);
        }
        return 0;
    }
}
